package com.dubious.interview.euler;

import org.joda.time.DateTime;

public class Problem14 {

    /**
     * The following iterative sequence is defined for the set of positive integers:
     * 
     * n n/2 (n is even) n 3n + 1 (n is odd)
     * 
     * Using the rule above and starting with 13, we generate the following sequence:
     * 
     * 13 40 20 10 5 16 8 4 2 1
     * 
     * It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms.
     * Although it has not been proved yet (Collatz Problem), it is thought that all starting
     * numbers finish at 1.
     * 
     * Which starting number, under one million, produces the longest chain?
     * 
     * NOTE: Once the chain starts the terms are allowed to go above one million.
     * 
     * @param args
     */
    public static void main(String[] args) {
        //@formatter:off
        // we will have an array of size N that contains the sequence length for all values m in [1,N]
        // when calculating the sequence for value m, if at any time we reach value p < m then we can
        // lookup the value for p in the array to help determine the sequence size
        //@formatter:on
        System.out.println("Start Time: " + new DateTime());

        int n = 1000000;
        int[] sequenceSize = new int[n];

        int maxSequenceSize = 1;
        int maxSequenceStart = 1;
        for (int i = 1; i < n; i++) {
            long currentValue = i;
            int currentSequenceSize = 1;
            while (true) {
                if (currentValue == 1) {
                    sequenceSize[i] = currentSequenceSize;
                    break;
                }

                currentSequenceSize++;
                if (currentValue % 2 == 0) {
                    // apply even rule
                    currentValue = currentValue / 2;
                } else {
                    // apply odd rule
                    currentValue = 3 * currentValue + 1;
                }

                if (currentValue < i) {
                    sequenceSize[i] = currentSequenceSize + sequenceSize[(int) currentValue];
                    // check if we have the max value so far
                    if (sequenceSize[i] > maxSequenceSize) {
                        maxSequenceSize = sequenceSize[i];
                        maxSequenceStart = i;
                    }

                    break;
                }
            }
        }

        System.out.println("Max Sequence Size: " + maxSequenceSize);
        // 557
        System.out.println("Max Sequence Start: " + maxSequenceStart);
        // 837799
        System.out.println("End Time: " + new DateTime());
        // in 400 ms
    }
}
